Shortest bridge [BFS, DFS]¶
Time: O(N^2); Space: O(N^2); medium
In a given 2D binary array A, there are two islands. (An island is a 4-directionally connected group of 1s not connected to any other 1s.)
Now, we may change 0s to 1s so as to connect the two islands together to form 1 island.
Return the smallest number of 0s that must be flipped. (It is guaranteed that the answer is at least 1.)
Example 1:
Input: A =
[
[0, 1],
[1, 0]
]
Output: 1
Example 2:
Input: A =
[
[0, 1, 0],
[0, 0, 0],
[0, 0, 1]
]
Output: 2
Example 3:
Input: A =
[
[1, 1, 1, 1, 1],
[1, 0, 0, 0, 1],
[1, 0, 1, 0, 1],
[1, 0, 0, 0, 1],
[1, 1, 1, 1, 1]
]
Output: 1
Notes:
1 <= len(A) = len(A[0]) <= 100
A[i][j] == 0 or A[i][j] == 1
1. Find and Grow¶
Intuition Conceptually, our method is very straightforward: find both islands, then for one of the islands, keep “growing” it by 1 until we touch the second island.
We can use a depth-first search to find the islands, and a breadth-first search to “grow” one of them. This leads to a verbose but correct solution.
Algorithm To find both islands, look for a square with a 1 we haven’t visited, and dfs to get the component of that region. Do this twice. After, we have two components source and target.
To find the shortest bridge, do a BFS from the nodes source. When we reach any node in target, we will have found the shortest distance.
Please see the code for more implementation details.
[3]:
import collections
class Solution1(object):
"""
Time: O(A), where A is the content of A.
Space: O(A).
"""
def shortestBridge(self, A):
"""
:type A: List[List[int]]
:rtype: int
"""
R, C = len(A), len(A[0])
def neighbors(r, c):
for nr, nc in ((r-1,c),(r,c-1),(r+1,c),(r,c+1)):
if 0 <= nr < R and 0 <= nc < C:
yield nr, nc
def get_components():
done = set()
components = []
for r, row in enumerate(A):
for c, val in enumerate(row):
if val and (r, c) not in done:
# Start dfs
stack = [(r, c)]
seen = {(r, c)}
while stack:
node = stack.pop()
for nei in neighbors(*node):
if A[nei[0]][nei[1]] and nei not in seen:
stack.append(nei)
seen.add(nei)
done |= seen
components.append(seen)
return components
source, target = get_components()
# print(source, target)
queue = collections.deque([(node, 0) for node in source])
done = set(source)
while queue:
node, d = queue.popleft()
if node in target: return d-1
for nei in neighbors(*node):
if nei not in done:
queue.append((nei, d+1))
done.add(nei)
[4]:
s = Solution1()
A = [[0,1],[1,0]]
assert s.shortestBridge(A) == 1
A = [[0,1,0],[0,0,0],[0,0,1]]
assert s.shortestBridge(A) == 2
A = [[1,1,1,1,1],[1,0,0,0,1],[1,0,1,0,1],[1,0,0,0,1],[1,1,1,1,1]]
assert s.shortestBridge(A) == 1
[7]:
import collections
class Solution2(object):
"""
Time: O(n^2)
Space: O(n^2)
"""
def shortestBridge(self, A):
"""
:type A: List[List[int]]
:rtype: int
"""
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
def get_islands(A):
islands = []
done = set()
for r, row in enumerate(A):
for c, val in enumerate(row):
if val == 0 or (r, c) in done:
continue
s = [(r, c)]
lookup = set(s)
while s:
node = s.pop()
for d in directions:
nei = node[0]+d[0], node[1]+d[1]
if not (0 <= nei[0] < len(A) and 0 <= nei[1] < len(A[0])) or \
nei in lookup or A[nei[0]][nei[1]] == 0:
continue
s.append(nei)
lookup.add(nei)
done |= lookup
islands.append(lookup)
if len(islands) == 2:
break
return islands
lookup, target = get_islands(A)
q = collections.deque([(node, 0) for node in lookup])
while q:
node, dis = q.popleft()
if node in target:
return dis-1
for d in directions:
nei = node[0]+d[0], node[1]+d[1]
if not (0 <= nei[0] < len(A) and 0 <= nei[1] < len(A[0])) or \
nei in lookup:
continue
q.append((nei, dis+1))
lookup.add(nei)
[8]:
s = Solution2()
A = [[0,1],[1,0]]
assert s.shortestBridge(A) == 1
A = [[0,1,0],[0,0,0],[0,0,1]]
assert s.shortestBridge(A) == 2
A = [[1,1,1,1,1],[1,0,0,0,1],[1,0,1,0,1],[1,0,0,0,1],[1,1,1,1,1]]
assert s.shortestBridge(A) == 1